﻿open System
open System.Diagnostics
open ClearLines.Bumblebee

[<DebuggerDisplay("{Name}")>]
type City = { Name: string; X: float; Y: float }

let Main =
   
   // Euclidean distance between cities
   let distance (C1, C2) = 
      (  (C1.X - C2.X) ** 2.0 + 
         (C1.Y - C2.Y) ** 2.0) ** 0.5

   // Permutation function: 
   // swaps items at first and second index
   let swap (first: int, second) index =
      if index = first then second
      elif index = second then first
      else index

   // Swap 2 random elements in an Array
   let randomSwap (rng: Random) items =
      let last = Array.length items
      let first = rng.Next(last)
      let second = rng.Next(last)
      Array.permute (fun i -> swap (first, second) i) items

   // Compute the total distance,
   // summing distances between consecutive cities
   let quality (circuit: City []) =
      let length = Array.length circuit
      [|
         for i in 0 .. (length - 1) ->
            distance(circuit.[i], circuit.[(i + 1) % length])
      |]
      |> Array.sum

   // determines if 2 pairs of cities intersect
   let intersects (city1, city2) (city3, city4) =
      let det1 = (city1.X - city3.X) * (city2.Y - city3.Y) - (city2.X - city3.X) * (city1.Y - city3.Y)
      let det2 = (city1.X - city4.X) * (city2.Y - city4.Y) - (city2.X - city4.X) * (city1.Y - city4.Y)
      let det3 = (city3.X - city1.X) * (city4.Y - city1.Y) - (city4.X - city1.X) * (city3.Y - city1.Y)
      let det4 = (city3.X - city2.X) * (city4.Y - city2.Y) - (city4.X - city2.X) * (city3.Y - city2.Y)
      (det1 * det2 <= 0.0) && (det3 * det4 <= 0.0)

   // Pick a random city in the circuit 
   // and look for an intersection afterwards.
   // If an intersection is found, remove the crossing
   let decross (rng: Random) (circuit: City []) =
      let length = Array.length circuit

      if length < 4 
      then circuit
      else
         let i = rng.Next(length - 3)
         let c1, c2 = circuit.[i], circuit.[i + 1]
      
         let intersection =
            seq { i + 2 .. length - 2 }  
            |> Seq.tryFind (fun i -> intersects (c1, c2) (circuit.[i], circuit.[i+1]))

         match intersection with
         | None -> circuit
         | Some(j) -> 
            let permutation x =
               if x > i && x <= j then i + j + 1 - x
               else x
            Array.permute permutation circuit

   // create an Array of cities on a circle:
   // that way, we know the best length is about 2*Pi*R
   let testRoute radius points = 
      let angle = Math.PI * 2.0 / (double)points
      [|
         for i in 1 .. points ->
            {  Name = i.ToString(); 
               X = Math.Cos(angle * (double) i) * radius; 
               Y = Math.Sin(angle * (double) i) * radius }           
      |]

   let rng = RNG.create()

   let root = testRoute 10.0 500 |> Array.shuffle rng

   let generator = fun (rng: Random) -> Array.shuffle rng root
   let mutator = fun (rng: Random) (circuit: City []) -> 
      let p = rng.NextDouble()
      if ( p < 0.1 ) 
      then decross rng circuit
      else randomSwap rng circuit

   let evaluator = fun (circuit: City []) -> - quality circuit
   
   let problem = new Problem<City []>(generator, mutator, evaluator)

   let displaySolution (circuit: City []) = 
      Array.iter (fun (c) -> Console.Write(c.Name + " ")) circuit

   let foundSomething = fun (msg: SolutionMessage<City []>) -> 
      Console.WriteLine("{0}, {1}", msg.DateTime.TimeOfDay, msg.Quality)
      // Console.WriteLine(displaySolution(msg.Solution))
      Console.WriteLine()
         
   let solver = new Solver<City []>()
   solver.FoundSolution.Add foundSomething

   Console.WriteLine("Press [Enter] to start")
   let wait = Console.ReadLine()
   Console.WriteLine("Starting: press [Enter] to stop search")   

   solver.Search problem |> ignore

   let wait = Console.ReadLine()
   solver.Stop()
   Console.WriteLine("Search stopped: press [Enter] to close")   
   
   let wait = Console.ReadLine()
   Console.WriteLine("Done")